package com.szh.zx.gaoDingJavaBook.chapter9;

/*
* *
* 自定义实现单向链表
*线性表-一对一
*   顺序结构-基于数组实现
*   链式结构-基于链表实现-单链表，双向链表，循环链表
* */

public class LinkListTest<T> {
//	定义一个内部类node node实例代表链表的节点
	private class Node{
//		保存节点数据
	private T data;
//	下个节点的引用
	private Node next;

	public Node() {
	}

	public Node(T data, Node next) {
		this.data = data;
		this.next = next;
	}

}
// 定义头结点，尾结点，以及节点数
	private Node header;
	private Node tail;
	private int size;
//  空链表
	public LinkListTest() {
		header = null;
		tail = null;
	}
//	以指定数据元素创建链表，该链表只有一个元素
	public LinkListTest(T element){
		header = new Node(element,null);
//		只有一个节点，header，tail都指向该节点
		tail = header;
		size++;
	}
	public int length(){
		return size;
	}
	public T get(int index){
		assert getNodeByIndex(index) != null;
		return getNodeByIndex(index).data;
	}
// 根据索引值获取指定的位置节点
	private Node getNodeByIndex(int index) {
		if (index < 0 || index>size-1){
			throw new IndexOutOfBoundsException("自定义线性表索引越界");
		}
//		从header 节点开始
		Node current = header;
		for (int i = 0; i < size && current !=null; i++, current =current.next) {
			if (i ==index){
				return current;
			}

		}
		return null;
	}
//	查找链式线性表中指定元素的索引
	public int locate(T element){
//		从头结点开始搜索
		Node current = header;
		for (int i = 0; i < size && current !=null; i++, current = current.next) {
			if (current.data.equals(element)){
				return i;
			}
		}
		return -1;
	}

//	向线性表的指定位置插入一个元素
	public void insert (T element, int index){
		if (index<0 || index>size){
			throw  new IndexOutOfBoundsException("自定义线性表插入数据索引值越界");
		}
		if (header == null){
			add(element);
		}
		else {
//			当index 为0 的时候从表头处开始插入
			if (index == 0){
				addAtHeader(element);
			}else {
//				获取插入点的前一个节点
				Node prev = getNodeByIndex(index -1);
//				让prev 的next 指向新节点，让新节点的next引用指向原来的prev 的下一个节点
				prev.next = new Node(element, prev.next);
				size++;
			}
		}
	}
//	 采用尾插法为链表添加新节点
	public void add(T element){
		if (header == null){
			header = new Node(element, null);
//			只有一个几点，header，tail 都指向该节点
			tail = header;
		}
		else {
//			创建新节点
			Node newNode = new Node(element, null);
//			让尾结点的next 指向新增的节点
			tail.next = newNode;
//			以新节点作为新的尾结点
			tail = newNode;
		}
		size ++;

	}
//	采用头茶法为链表添加新节点
	public void  addAtHeader(T element){
//		创建新节点，让新节点的next指向原来的header ,并且新节点作为新的header
		header = new Node(element, header);
//		如果插入之前是空链表
		if (tail == null){
			tail = header;

		}
		size++;
	}
//	删除链式线性表中指定的所引出的元素
	public T delete(int index){
		if (index<0 || index>size){
			throw  new IndexOutOfBoundsException("自定义线性表删除索引值越界");

		}
		Node del = null;
//		如果删除的是header节点
		if (index == 0){
			del = header;
			header = header.next;
		}else {
//			获取删除点的前一个节点
			Node prev = getNodeByIndex(index -1);
//			获取将要被删除的节点
			del = prev.next;
//			让被删除节点的next指向被删除节点的下一个节点
			prev.next = del.next;
//			将被删除节点的next引用赋值为null
			prev.next = del.next;
			// 将删除节点的next 引用赋值为null
			del.next = null;

		}
		size --;
		return del.data;
	}
//	删除链式表的最后一个元素
	public T remove(){
		return delete(size-1);
	}
//	判断链式表是否为空表
	public boolean empty(){
		return size ==0;
	}
// 清空线性表
	public void clear(){
//		将header 和 tail赋值为null
		header = null;
		tail=null;
		size=0;
	}

	@Override
	public String toString() {
//		链表为空链表时
		if (empty()){
			return "[]";
		}
		else {
			StringBuilder sb = new StringBuilder("[");
			for (Node current = header; current != null;current =current.next){
				sb.append(current.data.toString()+",");

			}
			int len = sb.length();
			return sb.delete(len-2,len).append("]").toString();
		}
	}












}
